package codetop.microsoft.T449;

import util.TreeNode;
import util.TreeUtil;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-10 11:17:42 星期六
 */
public class Codec {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        String s = new Codec().serialize(root);
        System.out.println(s);
        root = new Codec().deserialize(s);
        TreeUtil.printLevel(root);
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }

    private void preorder(TreeNode root, StringBuilder sb) {
        if (root == null)
            return;
        sb.append(root.val).append(",");
        preorder(root.left, sb);
        preorder(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0)
            return null;
        String[] ss = data.split(",");
        Integer[] preorder = Arrays.stream(ss).map(Integer::parseInt).toArray(Integer[]::new);
        Integer[] inorder = preorder.clone();
        Arrays.sort(inorder);
        return build(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    private TreeNode build(Integer[] preorder, Integer[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr)
            return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int k = -1;
        for (int i=il; i<=ir; ++i) {
            if (inorder[i] == preorder[pl]) {
                k = i;
                break;
            }
        }
        root.left = build(preorder, inorder, pl+1, k-il+pl, il, k-1);
        root.right = build(preorder, inorder, k-il+pl+1, pr, k+1, ir);
        return root;
    }
}